/*
*	链表
*/



//两数相加
//https://leetcode.cn/problems/add-two-numbers/submissions/
// class Solution {
// public:
//     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//         ListNode* head = new ListNode(-1); //头节点
//         ListNode* cur = head; //迭代节点

//         ListNode* cur1 = l1;
//         ListNode* cur2 = l2;
//         int next = 0; //进位数
//         while(cur1 || cur2 || next) //next进位了也需要创建最后一个节点
//         {
//             int num = 0;
//             if(cur1) 
//             {
//                 num += cur1->val;
//                 cur1 = cur1->next;
//             }
//             if(cur2)
//             {
//                 num += cur2->val;
//                 cur2 = cur2->next;
//             } 
//             num += next;
//             next = num/10;
//             while(num>9) num%=10;
//             cur->next = new ListNode(num);
//             cur = cur->next;
//         }
//         cur = head->next;
//         delete head;
//         return cur;
//     }
// };


//两两交换链表中的节点
//https://leetcode.cn/problems/swap-nodes-in-pairs/submissions/
// class Solution {
// public:
//     ListNode* swapPairs(ListNode* head) {
//         if(!head || !head->next) return head;

//         ListNode* newhead = new ListNode(-1);
//         newhead->next = head;
//         ListNode* prev = new ListNode(-1);
//         ListNode* cur = head;
//         ListNode* nnext = cur->next;
//         ListNode* nnnext = nnext->next;
//         ListNode* ret = nnext;
//         while(cur && nnext)
//         {
//             prev->next = nnext;
//             nnext->next = cur;
//             cur->next = nnnext;

//             prev = cur;
//             cur = nnnext;
//             if(cur) nnext = cur->next;
//             if(nnext) nnnext = nnext->next;
//         }
//         delete newhead;
//         return ret;
//     }
// };


 //重排链表
 //https://leetcode.cn/problems/reorder-list/submissions/
//  class Solution {
//  public:
//      void reorderList(ListNode* head) {
//          if (!head->next) return;
//          //1.找到中间节点
//          ListNode* prev = head, * cur = head;
//          ListNode* rever = nullptr;
//          ListNode* curprev = nullptr;
//          while (true) //偶数个在prev停 奇数在prev->next停下
//          {
//              if (!prev) //偶数个
//              {
//                  rever = cur;
//                  break;
//              }
//              else if (!prev->next) //奇数个
//              {
//                  curprev = cur;
//                  rever = cur->next;
//                  break;
//              }
//              prev = prev->next->next;
//              curprev = cur;
//              cur = cur->next;
//          }
//          curprev->next = nullptr;
//          //2.逆序后半部分链表
//          ListNode* newhead = new ListNode(-1);
//          while (rever)
//          {
//              ListNode* headnext = newhead->next;
//              ListNode* revernext = rever->next;
//              newhead->next = rever;
//              rever->next = headnext;
//              rever = revernext;
//          }
//          //3.合并链表
//          cur = newhead->next; //逆序链表
//          prev = newhead;
//          rever = head;
//          while (rever)
//          {
//              ListNode* revernext = rever->next;
//              prev->next = rever;
//              rever->next = cur;
//              prev = cur;
//              if(cur) cur = cur->next;
//              rever = revernext;
//          }
//          cur = newhead->next;
//          delete newhead;

//      }
//  };


 //合并k个升序链表
 //https://leetcode.cn/problems/merge-k-sorted-lists/submissions/
// class Solution {
// public:
//     ListNode* mergeKLists(vector<ListNode*>& lists) 
//     {
//         if(lists.size() == 0) return nullptr;
//         if(lists.size() == 1) return lists[0];

//         return mergo(lists,0,lists.size()-1);
//     }

//     ListNode* mergo(vector<ListNode*>& lists,int l,int r)
//     {
//         if(l>=r) return lists[l];

//         int mid = (l+r)/2;
        
//         ListNode* left = mergo(lists,l,mid);
//         ListNode* right = mergo(lists,mid+1,r);

//         //合并两个链表.
//         if(!left) return right;
//         if(!right) return left;

//         ListNode head;
//         head.next = nullptr;
//         ListNode* prev = &head;
//         while(left && right)
//         {
//             if(left->val < right->val)
//             {
//                 prev->next = left;
//                 left=left->next;
//             }
//             else
//             {
//                 prev->next = right;
//                 right=right->next;
//             }
//             prev = prev->next;
//         }
//         if(left) prev->next = left;
//         else if(right) prev->next = right;
//         return head.next;
//     }
// };


 //k个一组翻转链表
 //https://leetcode.cn/problems/reverse-nodes-in-k-group/submissions/
// class Solution {
// public:
//     ListNode* reverseKGroup(ListNode* head, int k) {
//         //求链表总数
//         int n = 0;
//         ListNode* cur = head;
//         while(cur)
//         {
//             ++n;
//             cur=cur->next;
//         }

//         //求出有几组需要翻转的链表
//         n /= k; 
//         cur = head; 
//         ListNode newhead; //头节点
//         ListNode* prev = &newhead;
//         //开始翻转n组 每一组翻转k个节点
//         for(int i = 0;i<n;++i)
//         {
//             ListNode* tmp = cur; //记录第一个节点 翻转后为最后一个节点 链接下一个翻转的链表
//             for(int j = 0;j<k;++j)
//             {
//                 ListNode* curnext = cur->next;
//                 cur->next = prev->next;
//                 prev->next = cur;
//                 cur = curnext;
//             }
//             prev = tmp; //下一次链接点变成当前已经翻转的最后一个节点
//         }
//         prev->next = cur; //此时cur后面的不足k个节点 直接连接
//         return newhead.next;
//     }
// };


